\ifx\wholebook\relax \else
% ------------------------

\documentclass[b5paper]{article}

\usepackage[en]{../../prelude}

\setcounter{page}{1}

\begin{document}

\title{Preface}

\author{LIU Xinyu
\thanks{{\bfseries LIU Xinyu } \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\maketitle
\fi

\markboth{Preface}{Elementary Algorithms}

Programmers learn elementary algorithms at school. Except for programming contest, code interview, they seldom use algorithms in commercial software development. When talking about algorithms in AI and machine learning, it actually means scientific modeling, but not about data structure or elementary algorithm. Even when programmers need them, they have already been provided in libraries. It seems quite enough to know about how to use the library as a tool but not `re-invent the wheel'.

I would say elementary algorithms are critical in solving `interesting problems', the usefulness of the problem set aside. Let's start with two problems.

\section{The smallest free number}
\label{min-free} \index{minimum free number}

Richard Bird gives an interesting programming problem to find the minimum number that not appears in a given list(Chapter 1, \cite{Bird-book}). It's common to use a number as the identifier (Id) to index entities. At any time, a number is either occupied or free. When client tries to acquire a new number as index, we want to always allocate the smallest available one. Suppose numbers are non-negative integers and those being occupied are recorded in a list, for example:

\begin{verbatim}
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
\end{verbatim}

How can we find the smallest free number, which is 10, from the list? It seems quite easy to figure out the solution.

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $x \gets 0$
  \Loop
    \If{$x \notin A$}
      \State \Return $x$
    \Else
      \State $x \gets x + 1$
    \EndIf
  \EndLoop
\EndFunction
\end{algorithmic}

Where the $\notin$ is realized like below.

\begin{algorithmic}[1]
\Function{`$\notin$'}{$x, X$}
  \For{$i \gets 1 $ to $|X|$}
    \If{$x = X[i]$}
      \State \Return False
    \EndIf
  \EndFor
  \State \Return True
\EndFunction
\end{algorithmic}

Some environments have built-in implementation to test if an element is in a list. Below is an example program.

\lstset{language=Python, frame=single}
\begin{lstlisting}
def minfree(lst):
    i = 0
    while True:
        if i not in lst:
            return i
        i = i + 1
\end{lstlisting}

However, when there are millions of numbers being used, this solution performs poor. The time spent is quadratic to the length of the list. In a computer with 2 cores of 2.10 GHz CPU, and 2G RAM, the C implementation takes 5.4s to search the minimum free number among 100,000 numbers, and takes more than 8 minutes to handle a million numbers.

\subsection{Improvement}
The key idea to improve the solution is based on the fact that, for $n$ numbers $x_1, x_2, ..., x_n$, if there exists free number, some $x_i$ must be outside the range $[0, n)$; otherwise the list is exactly some permutation of $0, 1, ..., n - 1$ hence $n$ should be returned as the minimum free number. In summary:

\be
\textit{minfree}(x_1, x_2, ..., x_n) \leq n
\label{min-free}
\ee

A better solution is to use an array of $n + 1$ flags to mark whether a number in range $[0, n]$ is free.

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $F \gets $[False, False, ..., False] where $|F| = n+1$
  \For{$\forall x \in A$}
    \If{$x < n$}
      \State $F[x] \gets$ True
    \EndIf
  \EndFor
  \For{$i \gets [0, n]$}
    \If{$F[i] =$ False}
      \State \Return $i$
    \EndIf
  \EndFor
\EndFunction
\end{algorithmic}

Line 2 initializes a flag array all of False values. Then we scan all numbers in $A$ and mark the corresponding flag to True if the value is less than $n$. Finally, we iterate to find the first False flag. This program takes time proportion to $n$. It uses $n + 1$ flags to cover the special case that $sorted(A) = [0, 1, 2, ..., n-1]$. This solution is much faster than the brute force one. In the same computer, the Python implementation takes 0.02s when dealing with 100,000 numbers.

Although this solution only takes $O(n)$ time, it needs additional $O(n)$ space to store the flags. We haven't tuned it yet. Each time the program allocates memory to create an array of $n + 1$ flags, then releases it when finish. Such memory allocation and release is expensive and cost a lot of processing time.

To improve it, we can allocate the memory in advance for later reusing, and change to bit-wise flags instead of array. For example as the following C program:

\begin{lstlisting}[language=C]
#define N 1000000
#define WORD_LENGTH (sizeof(int) * 8)

void setbit(unsigned int* bits, unsigned int i) {
    bits[i / WORD_LENGTH] |= 1 << (i % WORD_LENGTH);
}

int testbit(unsigned int* bits, unsigned int i) {
    return bits[i / WORD_LENGTH] & (1 << (i % WORD_LENGTH));
}

unsigned int bits[N / WORD_LENGTH + 1];

int minfree(int* xs, int n) {
  int i, len = N/WORD_LENGTH + 1;
  for (i = 0; i < len; ++i) {
      bits[i]=0;
  }
  for (i=0; i < n; ++i) {
      if(xs[i] < n) {
          setbit(bits, xs[i]);
      }
  }
  for (i=0; i <= n; ++i) {
      if (!testbit(bits, i)) {
          return i;
      }
  }
}
\end{lstlisting}

This program can handle 1 million numbers in 0.023s in the same computer.

\subsection{Divide and Conquer}
The above improvement costs $O(n)$ additional space for flags, can we eliminate it? The divide and conquer strategy is to break the problem into smaller ones, then solve them separately to get the answer.

We can put numbers $x_i \leq \lfloor n/2 \rfloor$ into a sub-list $A'$ and put the rest into another sub-list $A''$. According to (\ref{min-free}), if the length of $A'$ equals to $\lfloor n/2 \rfloor$, it means $A'$ is `full'. The minimum free number must be in $A''$. We can recursively search in $A''$ which is shorter the original list. Otherwise, it means the minimum free number is in $A'$, which again leads to a smaller problem.

When search in $A''$, the conditions change a bit. We do not start from $0$, but from $\lfloor n/2 \rfloor + 1$ as the new lower bound. We define the algorithm as $search(A, l, u)$, where $l$ is
the lower bound and $u$ is the upper bound index. For the empty list as a special case, we return the $l$ as the result.

\[
minfree(A) = search(A, 0, |A|-1)
\]

\[
\begin{array}{rcl}
search(\nil, l, u) & = & l \\
search(A, l, u) & = & \begin{cases}
       |A'| = m - l + 1 : & search(A'', m+1, u) \\
       otherwise : & search(A',  l, m) \\
\end{cases}
\end{array}
\]

where

\[ \begin{array}{rcl}
m & = & \displaystyle \lfloor \frac{l+u}{2} \rfloor \\
A' & = & [ x | x \in A, x \leq m ] \\
A''& = & [ x | x \in A, x > m ] \\
\end{array} \]

This algorithm doesn't need additional space\footnote{The recursion takes $O(\lg n)$ stack spaces, but it can be eliminated through tail recursion optimization}. Each recursive call performs $O(|A|)$ comparisons to build $A'$ and $A''$. After that the problem scale halves. Therefore, the time is bound to $T(n) = T(n/2) + O(n)$, which reduce to $O(n)$ according to master theorem. Alternatively, observe that the first call takes $O(n)$ to build $A'$ and $A''$ and the second call takes $O(n/2)$, and $O(n/4)$ for the third... The total time is $O(n + n/2 + n/4 + ...) = O(2n) = O(n)$. We use $[a | a \in A, p(a)]$ for list. It is different with $\{a | a \in A, p(a) \}$, which is a set.

Below example Haskell program implements this algorithm.

\begin{Haskell}
minFree xs = bsearch xs 0 (length xs - 1)

bsearch xs l u | xs == [] = l
               | length as == m - l + 1 = bsearch bs (m+1) u
               | otherwise = bsearch as l m
    where
      m = (l + u) `div` 2
      (as, bs) = partition (<=m) xs
\end{Haskell}

\subsection{Expressiveness and performance}
One may concern the performance of this divide and conquer algorithm. There are $O(\lg n)$ recursive calls, which need additional stack space. If wanted, we can eliminate the recursion:

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $l \gets 0, u \gets |A|$
  \While{$u - l > 0$}
    \State $m \gets l + \dfrac{u - l}{2}$
    \State $left \gets l$
    \For{$right \gets l$ to $u - 1$}
      \If{$A[right] \leq m$}
        \State $A[left] \leftrightarrow A[right]$
        \State $left \gets left + 1$
      \EndIf
    \EndFor
    \If{$left < m + 1$}
      \State $u \gets left$
    \Else
      \State $l \gets left$
    \EndIf
  \EndWhile
\EndFunction
\end{algorithmic}

As shown in figure \ref{fig:divide}, this program re-arranges the array such that all elements before $left$ are less than or equal to $m$; while those between $left$ and $right$ are greater than $m$.

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.7]{img/divide-by-m.ps}
  \caption{Divide the array, all $A[i] \leq m$ where $0 \leq i < left$; while all $A[i] > m$ where $left \leq i < right$. The rest elements haven't been processed yet.} \label{fig:divide}
\end{figure}

This solution is fast and needn't extra stack space. However, compare to the previous recursive one, there is some expressiveness drops. Depends on individual taste, one may prefer one over the other.

\section{Regular number}

The second puzzle is to find the 1,500-th number, which only contains factor 2, 3 or 5. Such numbers are called regular number, also known as 5-smooth indicating the greatest prime factor is at most 5, or Hamming numbers named after Richard Hamming in computer science. 2, 3, and 5 are of course regular numbers. $60 = 2^23^15^1$ is the 25-th number. $21 = 2^03^17^1$ is not valid because it has a factor 7. We consider $1=2^03^05^0$ be the 0-th regular number. The first 10 regular numbers are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

\subsection{The brute-force solution}
The straightforward way is to check numbers one by one from 1, extract all factors of 2, 3 and 5 to see if the left part is 1:

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \While{$n > 0$}
    \State $x \gets x + 1$
    \If{\Call{Valid?}{$x$}}
      \State $n \gets n - 1$
    \EndIf
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Valid?}{$x$}
  \While{$x \bmod 2 = 0$}
    \State $x \gets \lfloor x / 2 \rfloor$
  \EndWhile
  \While{$x \bmod 3 = 0$}
    \State $x \gets \lfloor x / 3 \rfloor$
  \EndWhile
  \While{$x \bmod 5 = 0$}
    \State $x \gets \lfloor x / 5 \rfloor$
  \EndWhile
  \State \Return $x = 1$ ?
\EndFunction
\end{algorithmic}

This `brute-force' algorithm works for small $n$. However, to find the 1500-th regular number (which is 860934420), its C implementation takes 40.39s in above computer. When $n$ increases to 15,000, it can't terminate after 10 minutes.

\subsection{Improvement}
Modular and divide calculations are very expensive \cite{Bentley}. And they are executed a lot in loops. Instead of checking if a number only contains 2, 3, or 5 as factors, we can construct regular number from these three factors. We can start from 1, multiply it with 2, 3, or 5 to generate the rest numbers. The problem turns to be how to generate regular numbers in order? One method is to utilize the queue data structure.

A queue allows to add element to one end (called enqueue), and delete from the other (called dequeue). The element enqueued first will be dequeued first. This nature is called FIFO (First In First Out). The idea is to add 1 as the first number to the queue. We repeatedly dequeue a number, multiply it with 2, 3, and 5, to generate 3 new numbers; then add them back to the queue in order. A new generated number may already exist in the queue. In such case, we drop the duplicated number. Because the new number may be smaller than the others in the queue, we must put them at the correct position. Figure \ref{fig:queues} shows this idea.

\begin{figure}[htbp]
  \centering
  \subcaptionbox{Initialize with 1}{\includegraphics[scale=0.5]{img/q1.ps}}
  \subcaptionbox{Add 2, 3, 5 back;}{\includegraphics[scale=0.5]{img/q2.ps}}
  \subcaptionbox{Add 4, 6, and 10 back;}{\includegraphics[scale=0.5]{img/q3.ps}}
  \subcaptionbox{Add 9 and 15 back, 6 is dropped.}{\includegraphics[scale=0.5]{img/q4.ps}}
  \caption{First 4 steps to generate regular numbers.}
  \label{fig:queues}
\end{figure}

We can design the algorithm based on this idea:

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $Q \gets \nil$
  \State $x \gets 1$
  \State \Call{Enqueue}{$Q, x$}
  \While{$n > 0$}
    \State $x \gets$ \Call{Dequeue}{$Q$}
    \State \Call{Unique-Enqueue}{$Q, 2x$}
    \State \Call{Unique-Enqueue}{$Q, 3x$}
    \State \Call{Unique-Enqueue}{$Q, 5x$}
    \State $n \gets n-1$
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Unique-Enqueue}{$Q, x$}
  \State $i \gets 0, m \gets |Q|$
  \While{$i < m$ and $Q[i] < x$}
    \State $i \gets i + 1$
  \EndWhile
  \If{$i \geq m$ or $x \neq Q[i]$}
    \State \Call{Insert}{$Q, i, x$}
  \EndIf
\EndFunction
\end{algorithmic}

The \textproc{insert} function takes $O(m)$ time to insert a number at proper position, where $m = |Q|$ is the length of the queue. It skips insertion if the number already exists. The length of the queue increases proportion to $n$ (Each time, we dequeue an element, and enqueue 3 new at most. The increase ratio $\leq$ 2), the total time is $O(1 + 2 + 3 + ... + n) = O(n^2)$.

Figure\ref{fig:big-O-1q} shows the number of access to the queue against $n$. It is a quadratic curve, which reflects the $O(n^2)$ performance.

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{img/big-O-1q.eps}
  \caption{Queue access count - $n$.} \label{fig:big-O-1q}
\end{figure}

The corresponding C implementation takes 0.016s to output 860934420. It is about 2500 times faster than the naive search solution.

We can also realize this improvement recursively. Suppose $X$ is an infinite list of all regular numbers $[x_1, x_2, x_3, ...]$. For every number, we multiply it by 2, the result is still a list of regular numbers: $[2x_1, 2x_2, 2x_3, ...]$. We can also multiply numbers in $X$ by 3 and 5, to generate two new infinite lists. If we merge them together, remove the duplicated numbers, and prepend 1 as the first, then we get $X$ again. In other words, the following equation holds:

\be
  X = 1 : [2x | \forall x \in X]\cup [3x | \forall x \in X] \cup [5x | \forall x \in X]
\ee

Where symbol $x : X$ means to link $x$ before list $X$, such that $x$ becomes the first element. It is called `cons' in Lisp. We link 1 before the rest, as it is the first regular number. To implement infinite lists merge, we define $\cup$ to recursively compare elements in two sorted lists. Let $X=[x_1, x_2, x_3...]$, $Y=[y_1, y_2, y_3, ...]$ be two such lists, $X' = [x_2, x_3, ...]$ and $Y'=[y_2, y_3, ...]$ contain the rest elements except without their heads $x_1$ and $y_1$. We define merge as below:

\[
X \cup Y = \begin{cases}
  x_1 < y_1: & x_1 : X' \cup Y \\
  x_1 = y_1: & x_1 : X' \cup Y' \\
  y_1 < x_1: & y_1 : X \cup Y' \\
\end{cases}
\]

We need not concern about either $X$ or $Y$ is empty, because they are both infinite lists. In functional settings that support lazy evaluation, this algorithm can be implemented as the following example program:

\begin{Haskell}
ns = 1 : (map (*2) ns) `merge` (map (*3) ns) `merge` (map (*5) ns)

merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                    | x == y = x : merge xs ys
                    | otherwise = y : merge (x:xs) ys
\end{Haskell}

The 1500th number 860934420 is given by \texttt{ns !! 1500}. In the same computer, it takes about 0.03s to output the answer.

\subsection{Queues}
Although the improved solution is much faster than the original brute-force one, it generates duplicated numbers, and they are eventually dropped. In order to keep numbers ordered, it needs linear time scan and insertion, which degrades the enqueue operation from constant time to $O(|Q|)$. To avoid duplication, we can separate all regular numbers into 3 disjoint buckets: $Q_2 = \{2^i | i > 0\}$, $Q_{23} = \{ 2^i3^j | i \geq 0, j > 0 \}$, and $Q_{235} = \{ 2^i3^j5^k | i,j \geq 0, k > 0\}$. The constraints that $j \neq 0$ in $Q_{23}$, and $k \neq 0$ in $Q_{235}$ ensure there is no overlap. The bucket is realized as a queue. They are initialized as $Q_2 = \{ 2 \}$, $Q_{23} = \{ 3\}$, and $Q_{235} = \{ 5 \}$. Starting from 1, each time we extract the smallest number $x$ from the three queues as the next regular number. Then do the following:

\begin{itemize}
\item If $x$ comes from $Q_2$, we enqueue $2x$, $3x$, and $5x$ back to $Q_2$, $Q_{23}$, and $Q_{235}$ respectively;
\item If $x$ comes from $Q_{23}$, we only enqueue $3x$ to $Q_{23}$, and $5x$ to $Q_{235}$. We should not add $2x$ to $Q_2$, because $Q_2$ cannot hold any numbers divided by 3.
\item If $x$ comes from $Q_{235}$, we only need enqueue $5x$ to $Q_{235}$. We should not add $2x$ to $Q_2$, or $3x$ to $Q_{23}$ because they can't hold numbers divided by 5.
\end{itemize}

We reach to the answer after repeatedly enqueue the smallest number $n$ times. The following algorithm implements this idea:

\begin{figure}[htbp]
  \centering
  \subcaptionbox{Enqueue 4, 6, 10;}{\includegraphics[scale=0.5]{img/q235-1.ps}}
  \subcaptionbox{Enqueue 9, 15;}{\includegraphics[scale=0.5]{img/q235-2.ps}}
  \subcaptionbox{Enqueue 8, 12, 20; }{\includegraphics[scale=0.5]{img/q235-3.ps}}
  \subcaptionbox{Enqueue 25.}{\includegraphics[scale=0.5]{img/q235-4.ps}}
  \caption{First 4 steps with $Q_2$, $Q_{23}$, and $Q_{235}$. They were initialize with 2, 3, 5.}
  \label{fig:q235}
\end{figure}

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \State $Q_2 \gets \{ 2 \}$, $Q_{23} \gets \{ 3 \}$, $Q_{235} \gets \{ 5 \}$
  \While{$n > 0$}
    \State $x \gets min$(\Call{Head}{$Q_2$}, \Call{Head}{$Q_{23}$}, \Call{Head}{$Q_{235}$})
    \If{$x =$ \Call{Head}{$Q_2$}}
      \State \Call{Dequeue}{$Q_2$}
      \State \Call{Enqueue}{$Q_2, 2x$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \ElsIf{$x=$ \Call{Head}{$Q_{23}$}}
      \State \Call{Dequeue}{$Q_{23}$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \Else
      \State \Call{Dequeue}{$Q_{235}$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \EndIf
    \State $n \gets n - 1$
  \EndWhile
  \State \Return $x$
\EndFunction
\end{algorithmic}

This algorithm loops on $n$. Each time it extracts the minimum number from the head of three queues. This takes constant time. Then it add at most 3 numbers to each queue respectively. This takes constant time too. Therefore the algorithm is bound to $O(n)$.

%% We can also define this solution recursively as a function $reg(n, [1], [2], [3], [5])$, where:

%% \[
%% \begin{array}{rcl}
%% reg(0, X, Q_2, Q_{23}, Q_{235}) & = & X \\
%% reg(n, X, Q_2, Q_{23}, Q_{235}) & = & reg(n - 1, X \doubleplus [x], Q_2', Q_{23}', Q_{235}') \\
%% \end{array}
%% \]

%% Where
%% \[
%%  x = min(head(Q_2), head(Q_{23}), head(Q_{235}))
%% \]
%% \[
%%  Q_2', Q_{23}', Q_{235}' = \begin{cases}
%%  x = head(Q_2) : & tail(Q_2) \doubleplus [2x], Q_{23} \doubleplus [3x], Q_{235} \doubleplus [5x] \\
%%  x = head(Q_{23}) : & Q_2, tail(Q_{23}) \doubleplus [3x], Q_{235} \doubleplus [5x] \\
%%  x = head(Q_{235}) : & Q_2, Q_{23}, tail(Q_{235}) \doubleplus [5x] \\
%% \end{cases}
%% \]

%% \begin{Haskell}
%% rs 0 xs _ _ _ = reverse xs
%% rs n xs q2 q3 q5 = rs (n - 1) (x : xs) q2' q3' q5'
%%     where
%%       x = minimum $ map head [q2, q3, q5]
%%       (q2', q3', q5')
%%         | x == head q2 = ((tail q2) ++ [2 * x], q3 ++ [3 * x], q5 ++ [5 * x])
%%         | x == head q3 = (q2, (tail q3) ++ [3 * x], q5 ++ [5 * x])
%%         | otherwise = (q2, q3, (tail q5) ++ [5 * x])
%% \end{Haskell} %$

%% Run \texttt{last \$ rs 1500 [1] [2] [3] [5]} generates the answer 860934420.

\section{Summary}
One might think the brute-force solution was sufficient to solve both programming puzzles. However, as the problem scales up, we have to seek for better solutions. There are many interesting problems, which were hard before, but through computer programming, we are able to solve them nowadays. This book aims to provide both functional and imperative definition for the commonly used elementary algorithms and data structures. We referenced many results from Okasaki's work\cite{okasaki-book} and classic text books(for example \cite{CLRS}). We try to avoid relying on a specific programming language, because it may or may not be familiar with the reader, and programming languages keep changing. Instead, we use pseudo code or mathematics notation to make the algorithm definition generic. When give code examples, the functional ones look more like Haskell, and the imperative ones look like a mix of C, Java, and Python. They are only for illustration purpose, but not guaranteed following any language specification strictly.

\begin{Exercise}
\Question{For the free number puzzle, since all numbers are not negative, we can leverage the sign as a flag to indicate a number exists. We can scan the number list, for every number $|x| < n$ (where $n$ is the length), negate the number at position $|x|$. Then we run another round of scan to find out the first positive number. It's position is the answer. Write a program to realize this method.}

\Question{There are $n$ numbers 1, 2, ..., $n$. After some processing, they are shuffled, and a number $x$ is altered to $y$. Suppose $1 \leq y \leq n$, design a solution to find $x$ and $y$ in linear time with constant space.}

\Question{Below example program is a solution for the regular number puzzle. Is it equivalent to the queue based solution?
\begin{lstlisting}[language = Bourbaki]
Int regularNum(Int m) {
    nums = Int[m + 1]
    n = 0, i = 0, j = 0, k = 0
    nums[0] = 1
    x2 = 2 * nums[i]
    x3 = 3 * nums[j]
    x5 = 5 * nums[k]
    while (n < m) {
        n = n + 1
        nums[n] = min(x2, x3, x5)
        if (x2 == nums[n]) {
            i = i + 1
            x2 = 2 * nums[i]
        }
        if (x3 == nums[n]) {
            j = j + 1
            x3 = 3 * nums[j]
        }
        if (x5 == nums[n]) {
            k = k + 1
            x5 = 5 * nums[k]
        }
    }
    return nums[m];
}
\end{lstlisting}
}
\end{Exercise}

\begin{thebibliography}{99}

\bibitem{Bird-book}
Richard Bird. ``Pearls of functional algorithm design''. Cambridge University Press; 1 edition (November 1, 2010). ISBN-10: 0521513383

\bibitem{Bentley}
Jon Bentley. ``Programming Pearls(2nd Edition)''. Addison-Wesley Professional; 2 edition (October 7, 1999). ISBN-13: 978-0201657883

\bibitem{okasaki-book}
Chris Okasaki. ``Purely Functional Data Structures''. Cambridge university press, (July 1, 1999), ISBN-13: 978-0521663502

\bibitem{CLRS}
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition''. The MIT Press, 2001. ISBN: 0262032937.

\end{thebibliography}

\ifx\wholebook\relax \else
\end{document}
\fi
